from stacking.warehouse.places.place import Place


class Stack(Place):
    """Represents a stack in a warehouse, i.e. a list of Item objects, inversion counter, earliest 
    due date, and height (sum of item thickness)."""
    is_stack = True
    
    def __init__(self, id, **meta):
        Place.__init__(self, id, **meta)
        self.items    = []     # [Item] - list of Item objects
        self.earliest = []     # [Item] - item with earliest due date
        self.inverted = []     # [Item] - items out of place
        self.height   = 0.0    # float - stack height (sum of item thickness)
        
    def __info__(self):
        due = self.earliest_due
        due = "inf" if due is None else due.end
        items = " ".join("i%s" % item.id for item in self.items)
        return "%s [inv=%d, due=%s] <%s>" % (self.id, self.inversions, due, items)
        
    def deepcopy(self, target=None):
        if target is None:
            cls = type(self)
            target = cls.__new__(cls)
        Place.deepcopy(self, target)
        target.items    = list(self.items)
        target.earliest = list(self.earliest)
        target.inverted = list(self.inverted)
        target.height   = self.height
        return target
        
    def _set_parent(self, warehouse):
        """Called *automatically* when the stack is connected to a warehouse."""
        if self.parent is not None:
            for item in self.items:
                self.parent.set_location(item, None)
        Place._set_parent(self, warehouse)
        if warehouse is not None:
            for item in self.items:
                warehouse.set_location(item, self)
                
    def clear(self):
        self.items    = []
        self.earliest = []
        self.inverted = []
        self.height   = 0.0
        
    def append(self, item):
        """Push an item into the top of the stack."""
        if len(self.items) == 0:
            self.earliest.append(item)
        else:
            # check if the item must be delivered before the item with earliest due
            earliest = self.earliest[-1]
            if due_compare(item, earliest) < 0:
                self.earliest.append(item)
            # otherwise check if an inversion was created
            elif inverted(earliest, item):
                self.inverted.append(item)
        self.items.append(item)
        self.height += item.thickness
        if self.parent is not None:
            self.parent.set_location(item, self)
            
    def pop(self):
        """Remove and return the item sitting at the top of the stack."""
        item = self.items.pop()
        if item is self.earliest[-1]:
            self.earliest.pop()
        if len(self.inverted) > 0 and item is self.inverted[-1]:
            self.inverted.pop()
        self.height -= item.thickness
        if self.parent is not None:
            self.parent.set_location(item, None)
        return item
        
    def insert(self, index, item):
        """A *very inefficient* method for inserting an item into a specific position in a 
        stack. This works by popping items until the desired index is at the top, pushing the 
        argument item, and then putting all the popped items back at the top of the stack. Use 
        sparingly."""
        above = []
        while len(self.items) > index:
            above.append(self.pop())
        self.append(item)
        while len(above) > 0:
            self.append(above.pop())
            
    def depth(self, item):
        """Return the 'depth' of an item in the stack, i.e. the number of other items above 
        the argument item."""
        return len(self.items) - self.items.index(item) - 1
        
    def items_above(self, item):
        """Returns a list of items which are placed above the argument item."""
        index = self.items.index(item) + 1
        return self.items[index:]
        
    def items_below(self, item):
        """Returns a list of items which are placed below the argument item."""
        index = self.items.index(item)
        return self.items[:index]
        
    def creates_inversion(self, item):
        """Returns True if pushing the item into the stack creates a new inversion."""
        if len(self.items) == 0:
            return False
        return inverted(self.earliest[-1], item)
        
    @property
    def empty(self):
        """True if the stack has no items."""
        return len(self.items) == 0
        
    @property
    def top(self):
        """Return the topmost item at the stack. An exception will be raised if the stack is 
        empty."""
        return self.items[-1]
        
    @property
    def earliest_item(self):
        """The item with the earliest due date, which will be the first to have to move."""
        return self.earliest[-1]
        
    @property
    def earliest_due(self):
        """The due date (interval) of the earliest moving item in the stack, or None if the 
        stack is empty."""
        return None if len(self.earliest) == 0 else self.earliest[-1].due
        
    @property
    def inversions(self):
        """Returns the number of inverted items in the stack."""
        return len(self.inverted)
        
    def __len__(self):
        return len(self.items)
        
    def __iter__(self):
        return iter(self.items)
        
        
def inverted(below, above):
    """Given two items ('below' and 'above'), returns true if above's due interval starts after 
    the end of the below's due interval. If a due interval is None, it is assumed that the 
    corresponding item will not leave the warehouse within the considered time horizon."""
    if below.due is None:
        return False
    if above.due is None:
        return True
    return above.due.start > below.due.end
    
    
def due_compare(A, B):
    """A comparator function for comparing two items by their due interval. Returns -1 if A's due 
    interval is smaller, +1 if B's due interval is smaller, or 0 if both items have the same due 
    interval. Note that when both items define a due interval, the intervals are compared first by 
    their end value, using the start value only as a tie breaker."""
    if A.due is None and B.due is None:
        return 0
    if A.due is None:
        return +1
    if B.due is None:
        return -1
    return cmp((A.due.end, A.due.start), (B.due.end, B.due.start))
    
    
